package com.gy.algorithm.carl.strexa;

import com.gy.designpattern.proxy.dynamic.cglib.TestReal;

/**
 * @BelongsProject: javabase
 * @BelongsPackage: com.gy.algorithm.carl
 * @Author: gy
 * @Date: 2024/10/22 11:30
 * @Description:
 */
public class RepeatedSubstringPattern459 {

    public static void main(String[] args) {

    }

    // end2 KMP
    public static boolean repeatedSubstringPattern(String s) {
        int[] next = getNext(s);
        int maxStr = next[next.length - 1];
        int minStr = s.length() - maxStr;
        return maxStr > 0 && s.length() % minStr == 0;
    }

    public static int[] getNext(String s){
        int[] res = new int[s.length()];

        res[0] = 0;

        int j = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) j = res[j - 1];
            if(s.charAt(i) == s.charAt(j)) j++;
            res[i] = j;
        }

        return res;
    }

    // end1 移出匹配
    public static  boolean repeatedSubstringPattern2(String s) {
        String newS = s + s;
        String substring = newS.substring(1, newS.length() - 1);
        return substring.contains(s);
    }

    // write
    public static boolean repeatedSubstringPattern1(String s) {
        int len = s.length();

        for (int i = 1; i * 2 <= len; i++) {
            if(len % i == 0){
                boolean match = true;
                for (int j = i; j < len; j++) {
                    if(s.charAt(j) != s.charAt(j - i)){
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }

        return false;
    }
}
